package com.sicheng.蓝桥.练习题.dp;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/12 16:45
 */
public class 数字三角形 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[][] nums = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1) {
                    nums[i][j] += nums[i - 1][j];
                } else if (j == i) {
                    nums[i][j] += nums[i - 1][j - 1];
                } else {
                    nums[i][j] += Math.max(nums[i - 1][j], nums[i - 1][j - 1]);
                }
            }
        }
        long res = -1;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, nums[n][i]);
        }

        System.out.println(res);
    }
}
